package com.xhh.learning.record.algorithm.knapsack;

/**
 * 类名： Knapsack
 * 描述： 0-1背包 动态规划
 * 作者： Administrator
 * 版本： V1.0
 * 创建时间:  2019/5/22 9:31
 * 最后修改时间:  2019/5/22 9:31
 */
public class Knapsack {

    public static void main(String[] args) {
        // knapsack(new int[]{2, 2, 4, 3, 6}, 5, 9);
        // knapsack1(new int[]{2, 2, 4, 6, 3}, new int[]{3, 4, 8, 9, 6}, 5, 9);
        // knapsack2(new int[]{40, 30, 80, 70, 90}, 5, 200);
        // int[][] matrix = {{5},{7,8},{2,3,4},{4,9,6,1},{2,7,9,4,5}};
        // knapsack3(matrix, 5);
        knapsack4(new int[]{1, 3, 5}, 3, 9);
    }

    /**
     * 单变量背包问题
     * @param weight
     * @param n
     * @param max
     */
    public static void knapsack(int[] weight, int n, int max) {
        boolean[] states = new boolean[max + 1];
        states[0] = true;
        states[weight[0]] = true;

        for (int i = 1; i < n; i++) {
            // 第i个物品放入背包，从后往前遍历
            for (int j = max - weight[i]; j >= 0; j--) {
                if (states[j]) {
                    states[j + weight[i]] = true;
                }
            }
        }

        // 输出
        for (int i = max; i >= 0; i--) {
            if (states[i]) {
                System.out.println(i);
                break;
            }
        }
    }


    /**
     *
     * @param weight 物品重量
     * @param values 物品价值
     * @param n 物品个数
     * @param max 背包最大容量
     */
    public static void knapsack1(int[] weight, int[] values,int n, int max) {
        int[] states = new int[max + 1];
        for (int i = 0; i < states.length; i++) {
            states[i] = -1;
        }

        states[0] = 0;
        states[weight[0]] = values[0];

        for (int i = 1; i < n; i++) {
            // 第i个物品放入背包
            for (int j = max - weight[i]; j >= 0; j--) {
                if (states[j] >= 0) {
                    int value = states[j] + values[i];
                    if (value > states[j + weight[i]]) {
                        states[j + weight[i]] = value;
                    }
                }
            }
        }

        // 输出
        int maxValue = -1;
        for (int i = 0; i <= max; i++) {
            if (states[i] > maxValue) {
                maxValue = states[i];
            }
        }
        System.out.println(maxValue);
    }


    public static void knapsack2(int[] values,int n, int max) {
        boolean[] states = new boolean[3 * max+1];
        for (int i = 0; i < states.length; i++) {
            states[i] = false;
        }

        states[0] = true;
        states[values[0]] = true;

        for (int i = 1; i < n; i++) {
            // 第i个物品放入背包
            for (int j = 3*max - values[i]; j >= 0; j--) {
                if (states[j]) {
                    states[j + values[i]] = true;
                }
            }
        }

        int i = max;
        for (; i <= 3*max; i++) {
            if (states[i]) {
                System.out.println("价格总额："+i);
                break;
            }
        }

        if (i == 3 * max + 1) {
            return;
        }

        // 输出购买物品
        for (int k = n-1; k >= 1; k--) {
            if (i-values[k]>=0 && states[i-values[k]]) {
                System.out.println("购买了：" + k);
                i = i-values[k];
            }
        }

        if (states[values[0]]) {
            System.out.println("购买了：0");
        }
    }

    /**
     * 杨辉三角 最长路径
     * @param matrix
     * @param n
     */
    public static void knapsack3(int[][] matrix,int n){
        int[] states = new int[n];
        states[0] = matrix[0][0];

        for (int i = 1; i < n; i++) {
            for (int j = matrix[i].length-1; j>=0; j--) {
                int value = matrix[i][j];
                if (j == 0) {
                    states[j] = states[j] + value;
                } else if (j == matrix[i].length - 1) {
                    states[j] = states[j-1] + value;
                } else {
                    int top1 = states[j-1] + value;
                    int top2 = states[j] + value;
                    states[j] =  Math.max(top1, top2);
                }
            }
        }

        int maxValue = -1;
        for (int state : states) {
            if (state > maxValue) {
                maxValue = state;
            }
        }
        System.out.println(maxValue);
    }

    /**
     * 我们有 3 种不同的硬币，1 元、3 元、5 元，我们要支付 9 元
     * 求最少需要多少个硬币
     *
     * @param money
     * @param n
     */
    public static void knapsack4(int[] money,int n,int max){
        int len = max / money[0];
        boolean[][] states = new boolean[len][max+1];

        for (int i = 0; i < money.length; i++) {
            states[0][money[i]] = true;
        }
        states[0][0] = true;

        int i;
        boolean flag = false;
        for (i = 1; i <= len && !flag; i++) {
            for (int j = 0; j < money.length; j++) {
                for (int k = max-money[j]; k >=0 ; k--) {
                    if (states[i-1][k]) {
                        states[i][k + money[j]] = true;
                    }
                    if (states[i][max]) {
                        flag = true;
                        break;
                    }
                }
            }
        }

        int temMax = max;
        for (int j = i-1; j >0 ; j--) {
            for (int k = 0; k < money.length; k++) {
                if (temMax - money[k] >=0) {
                    if (states[j-1][temMax - money[k]]) {
                        temMax = temMax - money[k];
                        System.out.println("item:" + money[k]);
                        break;
                    }
                }
            }
        }

        if (states[0][temMax]) {
            System.out.println("item:" + temMax);
        }

    }
}
